package com.linyaonan.zuochengyun._01._01;

import java.util.Arrays;

/**
 * @author: Lin
 * @date: 2022/7/24
 */
public class SimpleSort {

    public static void main(String[] args) {
        int[] o = {9,8,7,6,5,4,3,2,1,11,2,2,6,7,9,0,1};
        insertSort(o);
    }

    /**
     * 选择排序，就是将本轮数组中最小的放到数组的队头
     * @param org
     */
    public static void changeSort(int[] org) {
        if (org == null || org.length < 2) {
            return;
        }

        for (int i = 0; i < org.length - 1; i++) {
            int min = org[i];
            int minIndex = i;
            for (int j = i; j < org.length; j++) {
                if (org[j] < min) {
                    minIndex = j;
                    min = org[j];
                }
            }
            swap(org, i, minIndex);
        }
        System.out.println(Arrays.toString(org));
    }

    /**
     * 冒泡排序的过程是只要遇到比自己小的则交换，那么一轮下来后，最大的必然会落到队尾
     * 下一轮比较时就需要扣掉最后一位，一次类推
     * @param org
     */
    public static void bubbleSort(int[] org) {
        if (org == null || org.length < 2) {
            return;
        }
        for (int i = org.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (org[j] > org[j + 1]) {
                    swap(org,j,j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(org));
    }

    /**
     * 插入排序，认为前n-1项已经排好序，那么n项数据只需要依次向前比较，如果比前面的值小则交换，只到大于等于前面的值为止
     * @param org
     */
    public static void insertSort(int[] org) {
        if (org == null || org.length < 2) {
            return;
        }
        for (int i = 1; i < org.length; i++) {
            int p = i-1;
            while (p >=0 && org[i] < org[p]) {
                swap(org, i , i - 1);
                p--;
                i--;
            }
        }
        System.out.println(Arrays.toString(org));
    }

    /**
     * 数组原地交换
     * @param org
     * @param l
     * @param r
     */
    public static void swap(int[] org, int l, int r) {
        int tmp = org[l];
        org[l] = org[r];
        org[r] = tmp;
    }

}
